翻訳と辞書
Words near each other
・ PostYourBook
・ Postzygotic mutation
・ Postăvarul Massif
・ Postękalice
・ Postęp, Silesian Voivodeship
・ Postřekov
・ Postřelmov
・ Postřelmůvek
・ Postřižinské
・ Postřižín
・ Post–Civil Rights era in African-American history
・ Post–Cold War era
・ Post–Kyoto Protocol negotiations on greenhouse gas emissions
・ Post–Secondary Education Quality-Assessment Board
・ Post–September 11 anti-war movement
Post–Turing machine
・ Post–World War I recession
・ Post–World War II air-to-air combat losses
・ Post–World War II baby boom
・ Post–World War II demobilization strikes
・ Post–World War II economic expansion
・ Post–World War II legality of Nazi flags
・ Post–World War II Sherman tanks
・ Posua NIT Silchar
・ Posuchy
・ Posucice
・ Posuj
・ Posušje
・ Poswal
・ POSXML


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Post–Turing machine : ウィキペディア英語版
Post–Turing machine

:''The article Turing machine gives a general introduction to Turing machines, while this article covers a specific class of Turing machines.''
A Post–Turing machine is a "program formulation" of an especially simple type of Turing machine, comprising a variant of Emil Post's Turing-equivalent model of computation described below. (Post's model and Turing's model, though very similar to one another, were developed independently. Turing's paper was received for publication in May 1936, followed by Post's in October.) A Post–Turing machine uses a binary alphabet, an infinite sequence of binary storage locations, and a primitive programming language with instructions for bi-directional movement among the storage locations and alteration of their contents one at a time. The names "Post–Turing program" and "Post–Turing machine" were used by Martin Davis in 1973–1974 (Davis 1973, p. 69ff). Later in 1980, Davis used the name "Turing–Post program" (Davis, in Steen p. 241).
== 1936: Post model ==
In his 1936 paper "Finite combinatory processes—formulation 1" (which can be found on page 289 of ''The Undecidable''), Emil Post described a model of extreme simplicity which he conjectured is "logically equivalent to recursiveness", and which was later proved to be so. The quotes in the following are from this paper.
Post's model of a computation differs from the Turing-machine model in a further "atomization" of the acts a human "computer" would perform during a computation.
Post's model employs a "symbol space" consisting of a "two-way infinite sequence of spaces or boxes", each box capable of being in either of two possible conditions, namely "marked" (as by a single vertical stroke) and "unmarked" (empty). Initially, finitely-many of the boxes are marked, the rest being unmarked. A "worker" is then to move among the boxes, being in and operating in only one box at a time, according to a fixed finite "set of directions" (instructions), which are numbered in order (1,2,3,...,n). Beginning at a box "singled out as the starting point", the worker is to follow the set of instructions one at a time, beginning with instruction 1.
The instructions may require the worker to perform the following "basic acts" or "operations":
:(a) ''Marking the box he is in (assumed empty),''
:(b) ''Erasing the mark in the box he is in (assumed marked),''
:(c) ''Moving to the box on his right,''
:(d) ''Moving to the box on his left,''
:(e) ''Determining whether the box he is in, is or is not marked.''
Specifically, the ''i'' th "direction" (instruction) given to the worker is to be one of the following forms:
: (A) ''Perform operation Oi'' (= (a), (b), (c) ''or'' (d) ) ''and then follow direction ji'',
: (B) ''Perform operation'' (e) ''and according as the answer is yes or no correspondingly follow direction ji' or ji' ' '',
: (C) ''Stop''.
(The above indented text and italics are as in the original.) Post remarks that this formulation is "in its initial stages" of development, and mentions several possibilities for "greater flexibility" in its final "definitive form", including
: (1) replacing the infinity of boxes by a finite extensible symbol space, "extending the primitive operations to allow for the necessary extension of the given finite symbol space as the process proceeds",
: (2) using an alphabet of more than two symbols, "having more than one way to mark a box",
: (3) introducing finitely-many "physical objects to serve as pointers, which the worker can identify and move from box to box".

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Post–Turing machine」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.